package leetcode.eight;


import java.util.*;

/**
 * 并查集
 *
 * 图论:
 *
 */
public class Test {

    public static void main(String[] args) {

    }

    /**
     * LeetCode - 128 最长连续序列
     * 给定一个未排序的整数数组nums,找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度
     * 例如：nums = [100,4,200,1,3,2];
     *      输出:4 解释:最长数字连续序列是[1,2,3,4],他的长度是4
     *      nums = [0,3,7,2,5,8,4,6,0,1];
     *      输出:9
     */
    //hash表求解
    public static int longestConsecutive(int[] nums){
        //遍历数组,简历Hash表,可以自然去重
        Set<Integer> set= new HashSet<>();
        for (int num : nums){
           set.add(num);
        }
        int longest = 0;
        //遍历Hash表
        for (int num : set){
            int curr = num;
            //只有当num-1不存在时,才开始向后遍历mun+1,...
            if(!set.contains(curr - 1)){
                while (set.contains(curr + 1)){
                    curr++;
                }
            }
            //[num, curr]之间是连续的,数字有curr - num + 1 个
            longest = Math.max(longest, curr - num + 1);
        }
        return longest;
    }

    /**
     * LeetCode - 200 岛屿数量
     * 给你一个由'1'陆地和'0'水组成的二维网格,请你计算网格中岛屿的数量
     *  深度优先进行遍历
     */
    public static int numIslands(char[][] grid){
        if (grid == null || grid.length == 0){
            return 0;
        }
        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int row = 0; row < nr; row++){
            for (int col = 0; col < nc; col++){
                //当前元素是岛屿,进行深度遍历搜索
                if (grid[row][col] == '1'){
                    num_islands++;
                    dfs(grid, row, col);
                }
            }
        }
        return num_islands;
    }
    private static void dfs(char[][] grid, int row, int col) {
        int nr = grid.length;
        int nc = grid[0].length;
        //访问越界检查
        if(row < 0 || col < 0 || row >= nr || col >= nc || grid[row][col] == '0'){
            return;
        }
        //表示当前元素已经访问过了
        grid[row][col] = '0';
        //往当前元素的上下左右去试探
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }


    /**
     * LeetCode - 207 课程表
     * 输入:numCourses = 2,prerequisites = [[1,0]];
     * 输出:true
     * 解释:总共有2门课程,学习课程1之前,你需要完成课程0.这是课程的。
     */
    //深度优先遍历(基于出度表)实现
    public static boolean canFinish(int numCourses, int[][] prerequisites){
        //图的临接表
        List<List<Integer>> list= new ArrayList<>();
        for (int i = 0; i < numCourses; i++){
            list.add(new ArrayList<>());
        }
        for (int[] cp : prerequisites){
            list.get(cp[1]).add(cp[0]);
        }
        //用flags存放每个节点i(课程)的状态
        //初始未被访问：flag[i] = 0;从当前节点开始DFS访问,flag[i] = 1;当前节点完成DFS访问,flag[i] = -1;
        int[] flags = new int[numCourses];
        for (int i = 0; i < numCourses; i++){
            if(!dfsVertex(list,flags,i)){
                return false;
            }
        }
        return true;
    }
    private static boolean dfsVertex(List<List<Integer>> list, int[] flags, int i) {
        //深度遍历中节点i被第二次访问,说明有环。直接返回false
        if (flags[i] == 1){
            return false;
        }
        //当前访问节点已经处理过了,无需在重复搜索,直接返回true
        if (flags[i] == -1){
            return true;
        }
        //标记flags[i],从当前节点开始采用递归进行邻接顶点访问
        flags[i] = 1;
        for (Integer j : list.get(i)){
            if (!dfsVertex(list,flags,i)){
                return false;
            }
        }
        //当前节点完成dfs访问,访问过程中没有出现环,返回false
        flags[i] = -1;
        return true;
    }


}
